package com.klun.project.common.constans.leetcode;

/* 简洁明了的动态规划可以一试 */
public class Solution518 {
	/**
	 * 给定不同面额的硬币和一个总金额。
	 * 写出函数来计算可以凑成总金额的硬币组合数。
	 * 假设每一种面额的硬币有无限个。
	 */

	// 第二次尝试失败
	public int findArrayNum1(int[] coins, int amount) {
		int[] dp = new int[amount + 1];
		dp[0] = 1;
		for (int coin : coins) {
			int len = amount / coin;
			for (int i = coin; i < len + 1; i++) {
				if (i * (coin + 1) <= amount) {
					dp[i * (coin + 1)] = dp[i * coin] + 1;
				}
			}
		}
		return dp[amount];
	}
	// 第一次尝试失败
	public int findArrayNum(int[] coins, int amount) {
		int[] dp = new int[amount + 1];
		dp[0] = 1;
		for (int i = 0; i < coins.length; i++) {
			int coin = coins[i];
			for (int j = coin; j <= amount; j++) {
				dp[j] += dp[j - coin];
			}
		}
		return dp[amount];
	}


	/*
	动态规划
	转移方程
	每增加一种面额把数据筛选一遍
	则有 dp[i + coin] += dp[i]

	x:金币的面额
	dp[x] = n
	dp[x + coin] = 1
	*/
	public static int change(int amount, int[] coins) {
		int[] dp = new int[amount + 1];
		dp[0] = 1;
		for (int coin : coins) {
			for (int j = coin; j <= amount; j++) {
				dp[j] += dp[j - coin];
			}
		}
		return dp[amount];
	}


//	public static int change(int amount, int[] coins) {
//		int[] dp = new int[amount + 1];
//		dp[0] = 1;
//		for (int i = 0; i < coins.length; i++) {
//			int coin = coins[i];
//			for (int j = coin; j <= amount; j++) {
//				dp[j] += dp[j - coin];
//			}
//			System.out.println(Arrays.toString(dp));
//		}
//		return dp[amount];
//	}


	public static int zh(int amount, int[] coins, int start, int count) {
		if (start < 0 || amount < 0) {
			return 0;
		}
		if (amount == 0) {
			return 1;
		}
		count += zh(amount - coins[start], coins, start, count);
		count += zh(amount - coins[start], coins, start - 1, count);
		count += zh(amount, coins, start - 1, count);
		return count;
	}


	public static void main(String[] args) {
		Solution518 solution = new Solution518();
		int[] coins = {1, 2, 4, 5, 6, 7};
		System.out.println(solution.findArrayNum1(coins, 100));
		System.out.println(solution.findArrayNum(coins, 100));
	}
}